package com.cjm.algorithm.dp;

public class Ti377 {
    public static void main(String[] args) {
        Ti377 ti377 = new Ti377();
        ti377.combinationSum41(new int[]{1, 2, 3}, 4);
    }

    public int combinationSum41(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0]=1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                int num = nums[j];
                if (i-num>=0) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

    public int combinationSum4(int[] nums, int target) {
        // target是背包
        // nums是物品
        // 我们是先物品， 后背包
        int[] dp = new int[target+1];
        dp[0]=1;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            for (int j = num; j <= target; j++) {
                dp[j] += dp[j - num];
            }
        }
        return dp[target];
    }
}
